package org.leetcode.middle.leetcode19;


public class Solution
{

    public ListNode removeNthFromEnd5(ListNode head,int n){

        ListNode dummy =  new ListNode(-1,head);

        ListNode fast = dummy;
        ListNode slow = dummy;

        for (int i = 0; i <=n; i++) {
            fast = fast.next;
        }

        while (fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        slow.next=slow.next.next;

        return dummy.next;
    }


    /**
     * 双指针
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd3(ListNode head,int n)
    {

        ListNode dummyHead=new ListNode(0,head);

        ListNode fastIndex = dummyHead;
        ListNode slowIndex = dummyHead;

        //先让fast指针走n+1
        for (int i = 0; i <= n; i++) {
            fastIndex=fastIndex.next;
        }

        //fast和slow一起移动，当fast移动到链表的尾部时，slow移动的距离是:链表的长度-n =要删除节点的前一个节点
        while (fastIndex!=null)
        {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }


        slowIndex.next=slowIndex.next.next;

        return dummyHead.next;
    }

    public ListNode removeNthFromEnd2(ListNode head,int n) {
        if (head==null)
        {
            return head;
        }

        ListNode dummy=new ListNode(-1,head);

        int listLength = getListLength(dummy);

        int prevIndex = listLength-n;

        //被删除节点的前一个节点
        ListNode prev = getNodeByIndex(dummy, prevIndex);

        //被删除节点的后一个节点
        ListNode next=null;

        if (n>1)
        {
             next = getNodeByIndex(dummy, prevIndex + 2);
        }else {
             next = null;
        }

        prev.next=next;

        return dummy.next;
    }

    /**
     * 计算链表的长度
     * @param node
     * @return
     */
    public int getListLength(ListNode node)
    {
        int index = 0;

        while (node!=null)
        {
            index++;
            node=node.next;
        }

        return index;
    }

    /**
     * 获取指定的节点
     * @param node
     * @param target
     * @return
     */
    public ListNode getNodeByIndex(ListNode node,int target)
    {

        int index = 1;

        while (node!=null && index!=target)
        {
            index++;
            node = node.next;
        }

        return  node;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

//        ListNode listNode =new ListNode(1,new ListNode(2));
//        ListNode listNode =new ListNode(1);

        ListNode listNode1 = solution.removeNthFromEnd2(listNode, 2);


    }



}
